package code1.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 原题链接：https://leetcode.cn/problems/combination-sum-iii/
 */
public class P216 {

    List<List<Integer>> result;     //返回结果集
    int top=0;             //栈顶指针(指向栈顶元素)
    int[] stack;            //存放组合的栈

    public void backtracking(int k,int n,int begin,int curSum){
        if(top==k){
            if(curSum == n){
                List<Integer> list=new ArrayList<>();
                for(int i=1;i<=top;i++){
                    list.add(stack[i]);
                }
                result.add(list);
            }
            return;
        }
        for(int i=begin;i<=9;i++){
            stack[++top]=i;
            backtracking(k,n,i+1,curSum+i);
            top--;              //回溯
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        stack=new int[k+1];
        result=new ArrayList<>();
        backtracking(k,n,1,0);
        return result;
    }
}
